//无向图链表
#include<stdio.h>
typedef struct dui
{
    int date;
    struct dui*next;
}dui;
typedef struct duilie
{
    dui*head;
    dui*wei;
}duilie;
void chushi(duilie*dd)
{
    dd->head=dd->wei=NULL;
}
void charu(duilie*dd,int x)
{
    if(dd->head==NULL)
    {
        dd->head=(dui*)malloc(sizeof(dui));
        dd->head->date=x;
        dd->head->next=NULL;
        dd->wei=dd->head;
    }
    else
    {
        dui*newp=(dui*)malloc(sizeof(dui));
        newp->date=x;
        newp->next=NULL;
        dd->wei->next=newp;
        dd->wei=newp;
    }


}
int pankong(duilie*dd)
{
    return dd->head==NULL;
}
int qutou(duilie*dd)
{
    if(!pankong(dd))
    {
        return dd->head->date;
    }

}
void shanchu(duilie*dd)
{
    if(!pankong(dd))
    {
        dd->head=dd->head->next;
    }
}
typedef struct zibiao
{
    int xiabiao;//指向顶点下标的位置
    int quan;//权
    struct zibiao*next;
}zibiao;
typedef struct biaotou
{
    char ch;
    zibiao*next;
}biaotou;
typedef struct linjie
{
    biaotou*arr;//
    int *brr;//标记遍历过没有的数组
    int bian;
    int dian;
}linjie;
void chushihua(linjie*bb)
{
    printf("输入边数和点数\n");
    scanf("%d%d",&bb->bian,&bb->dian);
    getchar();
    bb->brr=(int *)malloc(sizeof(int )*bb->dian);
    int i=0;
    bb->arr=(biaotou*)malloc(sizeof(biaotou)*bb->dian);
    for(i=0;i<bb->dian;i++)//初始化顶点信息
    {
        printf("输入顶点的信息\n");
        scanf("%c",&(bb->arr[i].ch));
        getchar();
        bb->arr[i].next=NULL;
        bb->brr[i]=0;
    }
}
int find_hjx(linjie*bb,char ab)
{
    int i=0;
    for(i=0;i<bb->dian;i++)
    {
        if(ab==bb->arr[i].ch)
        {
            return i;
        }
    }
    return -1;
}
void tu_hjx(linjie*bb)
{
    int i=0;
    for(i=0;i<bb->bian;i++)
    {
        char a,b;
        int x;
        printf("输入两个顶点和权的大小\n");
        scanf("%c",&a);
        getchar();
        scanf("%c",&b);
        getchar();
        scanf("%d",&x);
        getchar();
        int i=find_hjx(bb,a);
        if(i==-1)
        {
            printf("输入的顶点不存在\n");
        }
        int j=find_hjx(bb,b);
        if(j==-1)
        {
            printf("输入的顶点不存在\n");
        }
        //j->i 头插法
        zibiao*newp=(zibiao*)malloc(sizeof(zibiao));
        newp->quan=x;
        newp->xiabiao=i;
        newp->next=bb->arr[j].next;
        bb->arr[j].next=newp;
        //i->j 头插法
        newp=(zibiao*)malloc(sizeof(zibiao));
        newp->quan=x;
        newp->xiabiao=j;
        newp->next=bb->arr[i].next;
        bb->arr[i].next=newp;
    }
}
void print(linjie*bb)
{
    int i=0;
    for(i=0;i<bb->dian;i++)
    {
        printf("%c ",bb->arr[i].ch);
        zibiao*tail=bb->arr[i].next;
        while(tail)
        {
            printf("下标%d 权%d ",tail->xiabiao,tail->quan);
            tail=tail->next;
        }
        printf("\n");
    }
}
void guangdu(linjie*bb,int i)
{
    duilie dl;
    chushi(&dl);
    charu(&dl,i);//先把第一个遍历的元素入队
    while(!pankong(&dl))//队列为空才结束循环
    {
        int ii=qutou(&dl);
        shanchu(&dl);
        if(bb->brr[ii]==0)//没有访问过该元素
        {
            printf("%c ",bb->arr[ii].ch);
            bb->brr[ii]=1;
        }
        zibiao*tail=bb->arr[ii].next;//设立一个移动元素
        while(tail)//为空时退出循环从新去上面取头
        {
            ii=tail->xiabiao;//取下标访问
            if(bb->brr[ii]==0)//检查有没有被访问过，如果没有就访问并且进栈
            {
                printf("%c ",bb->arr[ii].ch);
                bb->brr[ii]=1;
                charu(&dl,ii);
            }
            tail=tail->next;
        }
    }
}
int main()
{
    linjie bb;
    chushihua(&bb);
    tu_hjx(&bb);//生成图
    print(&bb);//测试
    guangdu(&bb,0);
    return 0;
}
